{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Lesson_7-REVISED.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.7.1"
    },
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Gc0HjM95fO1P"
      },
      "source": [
        "# Урок 7"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GbzywcdxfO1S"
      },
      "source": [
        "# Системы линейных уравнений. Часть 2"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "md8Xg102fO1T"
      },
      "source": [
        "## Существование и единственность решений систем линейных уравнений (продолжение)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WVZqJwlbfO1X"
      },
      "source": [
        "### Однородные системы"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "w-Q5ip_BfO1Z"
      },
      "source": [
        "Однородная система всегда совместна, так как в любом случае она будет иметь _тривиальное решение_: $x_{1}=x_{2}=...=x_{n}=0$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "AlNCeeGrfO1b"
      },
      "source": [
        "__Теорема__\n",
        "\n",
        "Если однородная квадратная (число уравнений равно числу неизвестных) СЛАУ имеет нетривиальное решение, то определитель матрицы коэффициентов равен нулю."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cn-Q53AkfO1c"
      },
      "source": [
        "__Следствие__\n",
        "\n",
        "Исходя из свойств определителя, можно заключить, что однородная система имеет __только тривиальное решение__, если ранг матрицы коэффициентов равен количеству неизвестных."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "rL3Oi6R8fO1d"
      },
      "source": [
        "__Пример__\n",
        "\n",
        "Выясним, имеет ли следующая система уравнений нетривиальные решения:\n",
        "\n",
        "$$\\begin{cases}\n",
        "x_{1}-x_{2}+2x_{3}=0, \\\\\n",
        "2x_{1}+x_{2}-3x_{3}=0, \\\\\n",
        "3x_{1}+2x_{3}=0.\n",
        "\\end{cases}$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "mFbNdtVFfO1e"
      },
      "source": [
        "Запишем матрицу коэффициентов и применим к ее строкам элементарные преобразования:\n",
        "\n",
        "$$\\begin{pmatrix}\n",
        "1 & -1 & 2 \\\\ \n",
        "2 & 1 & -3 \\\\ \n",
        "3 & 0 & 2 \n",
        "\\end{pmatrix}.$$\n",
        "\n",
        "Вычтем из второй строки первую, умноженную на $2$, и из третьей первую, умноженную на $3$:\n",
        "\n",
        "$$\\begin{pmatrix}\n",
        "1 & -1 & 2 \\\\ \n",
        "0 & 3 & -7 \\\\ \n",
        "0 & 3 & -4 \n",
        "\\end{pmatrix}.$$\n",
        "\n",
        "Вычтем из третьей строки вторую:\n",
        "\n",
        "$$\\begin{pmatrix}\n",
        "1 & -1 & 2 \\\\ \n",
        "0 & 3 & -7 \\\\ \n",
        "0 & 0 & 3 \n",
        "\\end{pmatrix}.$$\n",
        "\n",
        "Ранг матрицы равен $3$, как и число неизвестных, значит, система имеет только тривиальное решение $x_{1}=x_{2}=x_{3}=0$.\n",
        "\n",
        "Действительно, если теперь записать получившуюся систему, которая будет эквивалентна исходной,\n",
        "\n",
        "$$\\begin{cases}\n",
        "x_{1}-x_{2}+2x_{3}=0, \\\\\n",
        "3x_{2}-7x_{3}=0, \\\\\n",
        "3x_{3}=0,\n",
        "\\end{cases}$$\n",
        "\n",
        "проведя обратных ход метода Гаусса, несложно убедиться, что это решение единственно."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "lDRnd4yzfO1g"
      },
      "source": [
        "### Фундаментальная система решений"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Hx5YwJVmfO1h"
      },
      "source": [
        "__Определение__\n",
        "\n",
        "_Фундаментальная система решений (ФСР)_ однородной системы уравнений — это множество линейно независимых векторов $X_{i}=(x_{1},x_{2},...,x_{n})$, каждый из которых является решением однородной системы линейных уравнений.\n",
        "\n",
        "При этом любая линейная комбинация векторов из ФСР также является решением этой системы. \n",
        "\n",
        "То есть множество всех решений однородной СЛАУ будет образовывать линейное пространство (_пространство решений_), а ФСР будет базисом в этом линейном пространстве."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "iC_SHHjnfO1i"
      },
      "source": [
        "__Утверждение__\n",
        "\n",
        "Количество векторов фундаментальной системы решений равно разности количества неизвестных и ранга матрицы коэффициентов."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RApm4LTxfO1k"
      },
      "source": [
        "__Пример__\n",
        "\n",
        "Решим однородную систему\n",
        "\n",
        "$$\\begin{cases}\n",
        "3x_{1}+4x_{2}-x_{3}=0, \\\\\n",
        "x_{1}-3x_{2}+5x_{3}=0, \\\\\n",
        "4x_{1}+x_{2}+4x_{3}=0.\n",
        "\\end{cases}$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "nQnOJps_fO1l"
      },
      "source": [
        "Определитель матрицы коэффициентов\n",
        "\n",
        "$$\\begin{pmatrix}\n",
        "3 & 4 & -1 \\\\ \n",
        "1 & -3 & 5 \\\\ \n",
        "4 & 1 & 4 \n",
        "\\end{pmatrix}=0,$$\n",
        "\n",
        "значит, система имеет нетривиальные решения.\n",
        "\n",
        "Заметим, что третья строка является суммой первой и второй, а значит, по правилам элементарных преобразований, ее можно отбросить. Получим систему\n",
        "\n",
        "$$\\begin{cases}\n",
        "3x_{1}+4x_{2}-x_{3}=0, \\\\\n",
        "x_{1}-3x_{2}+5x_{3}=0.\n",
        "\\end{cases}$$\n",
        "\n",
        "Перенесем члены с $x_{3}$ в правую часть:\n",
        "\n",
        "$$\\begin{cases}\n",
        "3x_{1}+4x_{2}=x_{3}, \\\\\n",
        "x_{1}-3x_{2}=-5x_{3}.\n",
        "\\end{cases}$$\n",
        "\n",
        "Выразим $x_{1}$ из второй строки:\n",
        "\n",
        "$$x_{1}=3x_{2}-5x_{3},$$\n",
        "\n",
        "подставим в первую:\n",
        "\n",
        "$$3(3x_{2}-5x_{3})+4x_{2}=x_{3},$$\n",
        "\n",
        "$$9x_{2}-15x_{3}+4x_{2}=x_{3},$$\n",
        "\n",
        "$$13x_{2}=16x_{3},$$\n",
        "\n",
        "$$x_{2}=\\frac{16x_{3}}{13}$$\n",
        "\n",
        "и найдем $x_{1}$:\n",
        "\n",
        "$$x_{1}=3\\cdot\\frac{16x_{3}}{13}-5x_{3}=-\\frac{17x_{3}}{13}.$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "gQ3oShRhfO1m"
      },
      "source": [
        "$x_{3}$ может принимать бесконечное количество значений, а значит, мы можем записать общее решение системы вида $(-\\frac{17x_{3}}{13},\\frac{16x_{3}}{13}, x_{3})$.\n",
        "\n",
        "Можно убедиться в его правильности, приняв $x_{3}=1$, получив таким образом частное решение системы и подставив в исходную систему полученные значения неизвестных:\n",
        "\n",
        "$$\\begin{cases}\n",
        "3\\cdot(-\\frac{17}{13})+4\\cdot\\frac{16}{13}-1=0, \\\\\n",
        "-\\frac{17}{13}-3\\cdot\\frac{16}{13}+5=0, \\\\\n",
        "4\\cdot(-\\frac{17}{13})+\\frac{16}{13}+4=0.\n",
        "\\end{cases}$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "yeOCKVtWfO1o"
      },
      "source": [
        "Ответ запишем в виде линейной комбинации векторов ФСР (в данном случае такой вектор один):\n",
        "\n",
        "$$c\\left(-\\frac{17}{13},\\frac{16}{13}, 1\\right),$$\n",
        "\n",
        "где $c$ — любое вещественное число."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0IgxFvUlfO1p"
      },
      "source": [
        "### Взаимосвязь решений неоднородной и соответствующей однородной системы уравнений"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "bI1y_eIXfO1q"
      },
      "source": [
        "__Пример__\n",
        "\n",
        "Расмотрим систему уравнений\n",
        "\n",
        "$$\\begin{cases}\n",
        "x_{1}-x_{2}+x_{3}-x_{4}=4, \\\\\n",
        "x_{1}+x_{2}+2x_{3}+3x_{4}=8, \\\\\n",
        "2x_{1}+4x_{2}+5x_{3}+10x_{4}=20, \\\\\n",
        "2x_{1}-4x_{2}+x_{3}-6x_{4}=4. \\\\\n",
        "\\end{cases}$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "lcdyVAS3fO1s"
      },
      "source": [
        "Запишем расширенную матрицу системы:\n",
        "\n",
        "$$\\begin{pmatrix}\n",
        "\\left.\\begin{matrix}\n",
        "1 & -1 & 1 & -1 \\\\ \n",
        "1 & 1 & 2 & 3 \\\\ \n",
        "2 & 4 & 5 & 10 \\\\ \n",
        "2 & -4 & 1 & -6\n",
        "\\end{matrix}\\right|\n",
        "\\begin{matrix}\n",
        "4\\\\ \n",
        "8\\\\\n",
        "20\\\\\n",
        "4\n",
        "\\end{matrix}\n",
        "\\end{pmatrix},$$\n",
        "\n",
        "вычтем из второй строки первую, из третьей и четвертой вычтем первую, умноженную на 2:\n",
        "\n",
        "$$\\begin{pmatrix}\n",
        "\\left.\\begin{matrix}\n",
        "1 & -1 & 1 & -1 \\\\ \n",
        "0 & 2 & 1 & 4 \\\\ \n",
        "0 & 6 & 3 & 12 \\\\ \n",
        "0 & -2 & -1 & -4\n",
        "\\end{matrix}\\right|\n",
        "\\begin{matrix}\n",
        "4\\\\ \n",
        "4\\\\\n",
        "12\\\\\n",
        "-4\n",
        "\\end{matrix}\n",
        "\\end{pmatrix}.$$\n",
        "\n",
        "Последние три строки пропорциональны, значит, две из них можно убрать:\n",
        "\n",
        "$$\\begin{pmatrix}\n",
        "\\left.\\begin{matrix}\n",
        "1 & -1 & 1 & -1 \\\\ \n",
        "0 & 2 & 1 & 4 \\\\ \n",
        "\\end{matrix}\\right|\n",
        "\\begin{matrix}\n",
        "4\\\\ \n",
        "4\\\\\n",
        "\\end{matrix}\n",
        "\\end{pmatrix}.$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qMxkB_XBfO1t"
      },
      "source": [
        "Полученная система будет иметь вид\n",
        "\n",
        "$$\\begin{cases}\n",
        "x_{1}-x_{2}+x_{3}-x_{4}=4, \\\\\n",
        "~~~~~2x_{2}+x_{3}+4x_{4}=4. \\\\\n",
        "\\end{cases}$$\n",
        "\n",
        "Приняв $x_{3}=c_{3}$ и $x_{4}=c_{4}$, получим общее решение системы:\n",
        "\n",
        "$$x_{4}=c_{4},$$\n",
        "\n",
        "$$x_{3}=c_{3},$$\n",
        "\n",
        "$$x_{2} = 2 - \\frac{1}{2}c_{3} - 2c_{4},$$\n",
        "\n",
        "$$x_{1} = 6 - \\frac{3}{2}c_{3} - c_{4}.$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "G6-XpXPEfO1u"
      },
      "source": [
        "Рассмотрим теперь аналогичную систему, но однородную:\n",
        "$$\\begin{cases}\n",
        "x_{1}-x_{2}+x_{3}-x_{4}=0, \\\\\n",
        "x_{1}+x_{2}+2x_{3}+3x_{4}=0, \\\\\n",
        "2x_{1}+4x_{2}+5x_{3}+10x_{4}=0, \\\\\n",
        "2x_{1}-4x_{2}+x_{3}-6x_{4}=0. \\\\\n",
        "\\end{cases}$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0D5KbEYhfO1v"
      },
      "source": [
        "Повторим преобразования матрицы системы. Полученная система будет иметь вид\n",
        "\n",
        "$$\\begin{cases}\n",
        "x_{1}-x_{2}+x_{3}-x_{4}=0, \\\\\n",
        "~~~~~2x_{2}+x_{3}+4x_{4}=0, \\\\\n",
        "\\end{cases}$$\n",
        "\n",
        "и ее общим решением будет\n",
        "\n",
        "$$x_{4}=c_{4},$$\n",
        "\n",
        "$$x_{3}=c_{3},$$\n",
        "\n",
        "$$x_{2} = -\\frac{1}{2}c_{3} - 2c_{4},$$\n",
        "\n",
        "$$x_{1} = -\\frac{3}{2}c_{3} - c_{4}.$$\n",
        "\n",
        "_Если в общем решении больше одной свободной переменной, то классически выделяют совокупность, отвечающую простейшему базису $e_{1}=(1,0,0,...,0),~e_{2}=(0,1,0,...,0),...,e_{n-r}=(0,0,0,...,1)$, где $n$ — число неизвестных, $r$ — ранг матрицы коэффициентов._\n",
        "\n",
        "Положив $c_{3}=1$, $c_{4}=0$, а затем $c_{3}=0$, $c_{4}=1$, получим ФСР\n",
        "\n",
        "$$X_{1}=\\left(-\\frac{3}{2},-\\frac{1}{2},1,0\\right),~X_{2}=(-1,-2,0,1).$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "OOGq-CFTfO1x"
      },
      "source": [
        "__Утверждение 1__\n",
        "\n",
        "Сумма любого решения неоднородной системы линейных уравнений с любым решением соответствующей однородной системы представляет собой решение исходной неоднородной системы."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "rzdecq-rfO1y"
      },
      "source": [
        "Действительно, если $c_{1},...,c_{n}$ — решение неоднородной системы, а $d_{1},...,d_{n}$ — решение соответствующей ей однородной системы, то, подставив в $i$-е уравнение неоднородной системы вместо неизвестных числа $c_{1}+d_{1},...,c_{n}+d_{n}$, получим\n",
        "\n",
        "$$\\sum_{j=1}^{n}a_{ij}(c_{ij}+d_{ij})=\\sum_{j=1}^{n}a_{ij}c_{ij}+\\sum_{j=1}^{n}a_{ij}d_{ij} = b_{i}+0=b_{i}.$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "y8VsXnDYfO10"
      },
      "source": [
        "Покажем это на примере.\n",
        "\n",
        "Возьмем частное решение неоднородной системы, приняв $c_{3}=c_{4}=0$, тогда $x_{2}=2, ~ x_{1}=6$, и частное решение однородной системы, приняв $c_{3}=c_{4}=2$, тогда $x_{2}=-5, ~ x_{1}=-5$.\n",
        "\n",
        "Их сумма $X=(6-5,2-5,0+2,0+2)=(1,-3,2,2)$ будет решением неоднородной системы:\n",
        "\n",
        "$$\\begin{cases}\n",
        "1+3+2-2=4, \\\\\n",
        "1-3+2\\cdot2+3\\cdot2=8, \\\\\n",
        "2\\cdot1+4\\cdot(-3)+5\\cdot2+10\\cdot2=20, \\\\\n",
        "2\\cdot1-4\\cdot(-3)+2-6\\cdot2=4. \\\\\n",
        "\\end{cases}$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "HHMHi13GfO12"
      },
      "source": [
        "__Утверждение 2__ \n",
        "\n",
        "Разность двух произвольных решений неоднородной системы линейных уравнений является решением соответствующей однородной системы."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ErCtD0CtfO14"
      },
      "source": [
        "Действительно, если $c'_{1},...,c'_{n}$ и $c''_{1},...,c'_{n}$ — два произвольных решения неоднородной системы, то, подставив в любое $i$-е уравнение на место неизвестных числа $c'_{1}-c''_{1},...,c'_{n}-c''_{n}$, получим\n",
        "\n",
        "$$\\sum_{j=1}^{n}a_{ij}(c'_{ij}-c''_{ij})=\\sum_{j=1}^{n}a_{ij}c_{ij}-\\sum_{j=1}^{n}a_{ij}c''_{ij} = b_{i}-b_{i}=0.$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZgBsMeAfO15"
      },
      "source": [
        "Покажем это на примере.\n",
        "\n",
        "Возьмем два частных решения неоднородной системы, приняв $c_{3}=c_{4}=0$, тогда $x_{2}=2, ~ x_{1}=6$, и $c_{3}=c_{4}=2$, тогда $x_{2}=-3, ~ x_{1}=1$.\n",
        "\n",
        "Их разность $X=(6-1,2+3,0-2,0-2)=(5,5,-2,-2)$ будет решением неоднородной системы:\n",
        "\n",
        "$$\\begin{cases}\n",
        "5-5-2+2=0, \\\\\n",
        "5+5+2\\cdot(-2)+3\\cdot(-2)=0, \\\\\n",
        "2\\cdot5+4\\cdot5+5\\cdot(-2)+10\\cdot(-2)=0, \\\\\n",
        "2\\cdot5-4\\cdot5-2-6\\cdot(-2)=0. \\\\\n",
        "\\end{cases}$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "oHGAsjDWfO17"
      },
      "source": [
        "__Утверждение 3__\n",
        "\n",
        "_Сумма частного решения неоднородной системы и общего решения соответствующей однородной системы дает общее решение неоднородной системы_."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "nMCPuX2FfO1-"
      },
      "source": [
        "Это самое важное утверждение. Оно вытекает из двух предыдущих и иллюстрирует связь между решениями неоднородных и соответствующих им однородных систем уравнений."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "g14JTYQxfO1_"
      },
      "source": [
        "### Связь между ядром линейного преобразования и пространством решений"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "E2_pBijafO2B"
      },
      "source": [
        "Пространтсво $\\text{Ker}\\textbf{A}$ линейного оператора $\\textbf{A}$, задаваемого матрицей коэффициентов однородной системы уравнений $Ax=O$, совпадает с пространством решений этой однородной системы."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "fHY7nGlpfO2F"
      },
      "source": [
        "Следствием из этого утверждения, учитывая изученное в предыдущем разделе, является то, что множество решений неоднородной системы $Ax=b$ при наличии частного решения $x_{0}$ содержит в себе все векторы вида \n",
        "\n",
        "$$x_{0}+x^{*}, ~ x\\in\\text{Ker}\\textbf{A}.$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xOVQLfOcfO2H"
      },
      "source": [
        "## Другие методы решения СЛАУ"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PS9rgtxIfO2L"
      },
      "source": [
        "### Правило Крамера"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "fLI3XDo7fO2M"
      },
      "source": [
        "Для системы с $n$ уравнениями и $n$ неизвестными, если система уравнений невырождена (то есть $detA\\neq 0$), то система определена, то есть имеет единственное решение, и это решение может быть найдено по формулам Крамера:\n",
        "\n",
        "$$x_{i}=\\frac{detA_{i}}{detA},$$\n",
        "\n",
        "где $A_{i}$ — это матрица, получаемая заменой $i$-го столбца на вектор-столбец свободных членов $b$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "THL8It2YfO2O"
      },
      "source": [
        "__Пример__\n",
        "\n",
        "Решить методом Крамера систему линейных уравнений\n",
        "\n",
        "$$\\begin{cases}\n",
        "2x_{1}+3x_{2}-x_{3}=4, \\\\\n",
        "x_{1}+x_{2}+3x_{3}=5, \\\\\n",
        "3x_{1}-4x_{2}+x_{3}=0.\n",
        "\\end{cases}$$\n",
        "\n",
        "__Решение__\n",
        "\n",
        "Найдем определитель матрицы коэффициентов:\n",
        "\n",
        "$$detA=\\begin{vmatrix}\n",
        "2 & 3 & -1\\\\ \n",
        "1 & 1 & 3\\\\ \n",
        "3 & -4 & 1\n",
        "\\end{vmatrix}=\n",
        "2\\begin{vmatrix}\n",
        "1 & 3\\\\ \n",
        "-4 & 1 \n",
        "\\end{vmatrix}-\n",
        "3\\begin{vmatrix}\n",
        "1 & 3\\\\ \n",
        "3 & 1 \n",
        "\\end{vmatrix}-\n",
        "\\begin{vmatrix}\n",
        "1 & 1 \\\\ \n",
        "3 & -4\n",
        "\\end{vmatrix}=2(1 \\cdot 1-3\\cdot (-4))-3(1\\cdot 1-3\\cdot 3)-1(1\\cdot (-4)-3\\cdot 1)=57\\neq 0,$$\n",
        "\n",
        "следовательно, система совместна.\n",
        "\n",
        "Найдем определители $detA_{1}$, $detA_{2}$, $detA_{3}$:\n",
        "\n",
        "$$detA_{1}=\\begin{vmatrix}\n",
        "4 & 3 & -1\\\\ \n",
        "5 & 1 & 3\\\\ \n",
        "0 & -4 & 1\n",
        "\\end{vmatrix}=\n",
        "4\\begin{vmatrix}\n",
        "1 & 3\\\\ \n",
        "-4 & 1 \n",
        "\\end{vmatrix}-\n",
        "5\\begin{vmatrix}\n",
        "3 & -1\\\\ \n",
        "-4 & 1 \n",
        "\\end{vmatrix}+\n",
        "0\\begin{vmatrix}\n",
        "3 & -1 \\\\ \n",
        "1 & 3\n",
        "\\end{vmatrix}=4(1 \\cdot 1-3\\cdot (-4))-5(3\\cdot (-1)-(-4)\\cdot (-1))=57,$$\n",
        "\n",
        "$$detA_{2}=\\begin{vmatrix}\n",
        "2 & 4 & -1\\\\ \n",
        "1 & 5 & 3\\\\ \n",
        "3 & 0 & 1\n",
        "\\end{vmatrix}=\n",
        "2\\begin{vmatrix}\n",
        "5 & 3\\\\ \n",
        "0 & 1 \n",
        "\\end{vmatrix}-\n",
        "4\\begin{vmatrix}\n",
        "1 & 3\\\\ \n",
        "3 & 1 \n",
        "\\end{vmatrix}-\n",
        "\\begin{vmatrix}\n",
        "1 & 5 \\\\ \n",
        "3 & 0\n",
        "\\end{vmatrix}=2(5 \\cdot 1-0\\cdot 3)-4(1\\cdot 1-3\\cdot 3)-1(1\\cdot 0-3\\cdot 5)=57,$$\n",
        "\n",
        "$$detA_{3}=\\begin{vmatrix}\n",
        "2 & 3 & 4\\\\ \n",
        "1 & 1 & 5\\\\ \n",
        "3 & -4 & 0\n",
        "\\end{vmatrix}=\n",
        "2\\begin{vmatrix}\n",
        "1 & 5\\\\ \n",
        "-4 & 0 \n",
        "\\end{vmatrix}-\n",
        "3\\begin{vmatrix}\n",
        "1 & 5\\\\ \n",
        "3 & 0 \n",
        "\\end{vmatrix}+\n",
        "4\\begin{vmatrix}\n",
        "1 & 1 \\\\ \n",
        "3 & -4\n",
        "\\end{vmatrix}=2(1 \\cdot 0-(-4)\\cdot 5)-3(1\\cdot 0-5\\cdot 3)-1(1\\cdot (-4)-3\\cdot 1)=57.$$\n",
        "\n",
        "Найдем решение по формулам Крамера:\n",
        "\n",
        "$$x_{1} = \\frac{detA_{1}}{detA} = \\frac{57}{57}=1,$$\n",
        "\n",
        "$$x_{2} = \\frac{detA_{2}}{detA} = \\frac{57}{57}=1,$$\n",
        "\n",
        "$$x_{3} = \\frac{detA_{3}}{detA} = \\frac{57}{57}=1.$$\n",
        "\n",
        "_Следует помнить, что правило Крамера применимо только к системам, в которых количество уравнений совпадает с количеством неизвестных._"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LlKgjl7TfO2P"
      },
      "source": [
        "### LU-разложение"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PFA_I6X0fO2Q"
      },
      "source": [
        "Этот метод — модификация метода Гаусса, придуманная Аланом Тьюрингом в 1948 году."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "YTjIkg0FMV9X"
      },
      "source": [
        ""
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "P6EM5MnlfO2T"
      },
      "source": [
        "__Теорема__\n",
        "\n",
        "Пусть дана квадратная матрица $A$ порядка $n$, и $A_{k}$ — главный минор этой матрицы, составленный из первых $k$ строк и столбцов. Если $det(A_{k})\\neq0$ для $k=1,2,...,n-1$, тогда существует единственная нижняя треугольная матрица $L=(l_{ij})$, где $l_{11}=l_{22}=...=l_{nn}=1$, и единственная верхняя треугольная матрица $U=(u_{ij})$, такие, что $LU=A$. Более того, $det(A)=u_{11}\\cdot u_{22}\\cdot...\\cdot u_{nn}$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "bf4gKSlKfO2U"
      },
      "source": [
        "Представление матрицы системы уравнений $A$ в виде произведения $LU$ является основной идеей гауссовских схем исключения, так как система $Ax=b$ может быть записана как\n",
        "\n",
        "$$LUx=b$$\n",
        "\n",
        "и сводится к двум системам с треугольными матрицами."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "G3bg4hvUfO2W"
      },
      "source": [
        "Если принять $Ux=y$, то получим\n",
        "\n",
        "$$Ly=b.$$\n",
        "\n",
        "Так как $L$ — нижняя треугольная матрица, компоненты промежуточного решения $y$ могут быть получены просто путем последовательной подстановки, так как первое уравнение содержит только $y_{1}$, второе —  $y_{1}$ и  $y_{2}$ и т. д.\n",
        "\n",
        "Вторым шагом, когда мы нашли $y$, решается система\n",
        "\n",
        "$$Ux=y,$$\n",
        "\n",
        "где $U$ — верхняя треугольная матрица, то есть эта система также решается простой последовательной подстановкой в обратном порядке: $x_{n}, x_{n-1},...,x_{1}$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "HT4WXDhQfO2X"
      },
      "source": [
        "Вычисление $L$ и $U$ вместе с решением системы $Ly=b$ обычно называется _прямым исключением_, а решение системы $Ux=y$ — _обратной подстановкой_."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "jgySKY-hfO2Y"
      },
      "source": [
        "Опишем алгоритм получения $LU$-разложения на примере квадратной системы уравнений с $n=4$. Общий случай легко получится из этих представлений:\n",
        "\n",
        "$$\\begin{pmatrix}\n",
        "a_{11} & a_{12} & a_{13} & a_{14}\\\\ \n",
        "a_{21} & a_{22} & a_{23} & a_{24}\\\\ \n",
        "a_{31} & a_{32} & a_{33} & a_{34}\\\\ \n",
        "a_{41} & a_{42} & a_{43} & a_{44}\\\\ \n",
        "\\end{pmatrix}\n",
        "\\begin{pmatrix}\n",
        "x_{1}\\\\ \n",
        "x_{2}\\\\ \n",
        "x_{3}\\\\ \n",
        "x_{4}\\\\ \n",
        "\\end{pmatrix}=\n",
        "\\begin{pmatrix}\n",
        "b_{1}\\\\ \n",
        "b_{2}\\\\ \n",
        "b_{3}\\\\ \n",
        "b_{4}\\\\ \n",
        "\\end{pmatrix}.$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BIPWWPH7fO2a"
      },
      "source": [
        "Верхняя треугольная матрица $U$ получается путем прямого хода метода Гаусса.\n",
        "\n",
        "Повторяя алгоритм из предыдущего урока, если $a_{11}\\neq0$, на первом шаге умножаем первое уравнение на \n",
        "\n",
        "$$m_{i1}=\\frac{a_{i1}}{a_{11}}$$\n",
        "\n",
        "и вычитаем его из $i$-го ($i=2,3,4$).\n",
        "\n",
        "В итоге получаем эквивалентную систему\n",
        "\n",
        "$$\\begin{pmatrix}\n",
        "a_{11} & a_{12} & a_{13} & a_{14}\\\\ \n",
        "0 & a_{22}^{(1)} & a_{23}^{(1)} & a_{24}^{(1)}\\\\ \n",
        "0 & a_{32}^{(1)} & a_{33}^{(1)} & a_{34}^{(1)}\\\\ \n",
        "0 & a_{42}^{(1)} & a_{43}^{(1)} & a_{44}^{(1)}\\\\ \n",
        "\\end{pmatrix}\n",
        "\\begin{pmatrix}\n",
        "x_{1}\\\\ \n",
        "x_{2}\\\\ \n",
        "x_{3}\\\\ \n",
        "x_{4}\\\\ \n",
        "\\end{pmatrix}=\n",
        "\\begin{pmatrix}\n",
        "b_{1}\\\\ \n",
        "b_{2}^{1}\\\\ \n",
        "b_{3}^{1}\\\\ \n",
        "b_{4}^{1}\\\\ \n",
        "\\end{pmatrix},$$\n",
        "\n",
        "где\n",
        "\n",
        "$$a_{ij}^{(1)}=a_{ij}-a_{1j}\\frac{a_{i1}}{a_{11}}~~~~(i,j\\geq2),$$\n",
        "$$b_{i}^{(1)}=b_{i}-b_{1}\\frac{a_{i1}}{a_{11}}.$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3Ugk2aHqfO2b"
      },
      "source": [
        "Если $a_{11}=0$, тогда можем выбрать главный элемент по столбцу или строке: находим строку (столбец) в матрице с максимальным по модулю первым элементом и меняем эту строку (столбец) местами с первой строкой (столбцом)."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0kdfYtWjfO2c"
      },
      "source": [
        "Запишем получившуюся систему в виде\n",
        "\n",
        "$$A^{1}x=b^{1}.$$\n",
        "\n",
        "Если $M_{1}$ — нижняя треугольная матрица\n",
        "\n",
        "$$M_{1}=\\begin{pmatrix}\n",
        "1 & 0 & 0 & 0\\\\ \n",
        "-m_{21} & 1 & 0 & 0\\\\ \n",
        "-m_{31} & 0 & 1 & 0\\\\ \n",
        "-m_{41} & 0 & 0 & 1\\\\ \n",
        "\\end{pmatrix},$$\n",
        "\n",
        "то\n",
        "\n",
        "$$A^{(1)}=M_{1}A,~~~b^{(1)}=M_{1}b.$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "v9SjI0ULfO2e"
      },
      "source": [
        "Если $a_{22}^{(1)}\\neq 0$, то проведем второй шаг метода Гаусса: умножим второе уравнение на \n",
        "\n",
        "$$m_{i2}=\\frac{a_{i2}^{(1)}}{a_{22}^{(1)}}$$\n",
        "\n",
        "и вычтем его из $i$-го ($i=3,4$).\n",
        "\n",
        "Получим систему\n",
        "\n",
        "$$\\begin{pmatrix}\n",
        "a_{11} & a_{12} & a_{13} & a_{14}\\\\ \n",
        "0 & a_{22}^{(1)} & a_{23}^{(1)} & a_{24}^{(1)}\\\\ \n",
        "0 & 0& a_{33}^{(2)} & a_{34}^{(2)}\\\\ \n",
        "0 & 0& a_{43}^{(2)} & a_{44}^{(2)}\\\\ \n",
        "\\end{pmatrix}\n",
        "\\begin{pmatrix}\n",
        "x_{1}\\\\ \n",
        "x_{2}\\\\ \n",
        "x_{3}\\\\ \n",
        "x_{4}\\\\ \n",
        "\\end{pmatrix}=\n",
        "\\begin{pmatrix}\n",
        "b_{1}\\\\ \n",
        "b_{2}^{1}\\\\ \n",
        "b_{3}^{2}\\\\ \n",
        "b_{4}^{2}\\\\ \n",
        "\\end{pmatrix},$$\n",
        "\n",
        "где\n",
        "\n",
        "$$a_{ij}^{(2)}=a_{ij}^{(1)}-a_{2j}^{(1)}\\frac{a_{i2}^{(1)}}{a_{22}^{(1)}}~~~~(i,j\\geq3),$$\n",
        "$$b_{i}^{(2)}=b_{i}^{(1)}-b_{2}^{(1)}\\frac{a_{i2}^{(1)}}{a_{22}^{(1)}}.$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PV0TqsEDfO2f"
      },
      "source": [
        "Запишем систему в виде\n",
        "\n",
        "$$A^{2}x=b^{2},$$\n",
        "\n",
        "причем\n",
        "\n",
        "$$A^{(2)}=M_{2}A^{(1)},~~~b^{(2)}=M_{2}b^{(1)},$$\n",
        "\n",
        "где $M_{2}$ — нижняя треугольная матрица\n",
        "\n",
        "$$M_{2}=\\begin{pmatrix}\n",
        "1 & 0 & 0 & 0\\\\ \n",
        "0 & 1 & 0 & 0\\\\ \n",
        "0 & -m_{32} & 1 & 0\\\\ \n",
        "0 & -m_{42} & 0 & 1\\\\ \n",
        "\\end{pmatrix}.$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "FZrpPY7ufO2g"
      },
      "source": [
        "Наконец, предполагая, что $a_{33}^{2}\\neq0$, умножим третье уравнение на \n",
        "\n",
        "$$m_{i3}=\\frac{a_{i3}^{(2)}}{a_{33}^{(2)}}$$ \n",
        "\n",
        "и вычтем его из $i$-го (здесь i=4). Получим\n",
        "\n",
        "$$\\begin{pmatrix}\n",
        "a_{11} & a_{12} & a_{13} & a_{14}\\\\ \n",
        "0 & a_{22}^{(1)} & a_{23}^{(1)} & a_{24}^{(1)}\\\\ \n",
        "0 & 0 & 0 & a_{34}^{(2)}\\\\ \n",
        "0 & 0 & 0 & a_{44}^{(3)}\\\\ \n",
        "\\end{pmatrix}\n",
        "\\begin{pmatrix}\n",
        "x_{1}\\\\ \n",
        "x_{2}\\\\ \n",
        "x_{3}\\\\ \n",
        "x_{4}\\\\ \n",
        "\\end{pmatrix}=\n",
        "\\begin{pmatrix}\n",
        "b_{1}\\\\ \n",
        "b_{2}^{1}\\\\ \n",
        "b_{3}^{2}\\\\ \n",
        "b_{4}^{3}\\\\ \n",
        "\\end{pmatrix},$$\n",
        "\n",
        "где\n",
        "\n",
        "$$a_{ij}^{(3)}=a_{ij}^{(2)}-a_{3j}^{(2)}\\frac{a_{i3}^{(2)}}{a_{33}^{(2)}}~~~~(i,j\\geq4),$$\n",
        "$$b_{i}^{(3)}=b_{i}^{(2)}-b_{3}^{(2)}\\frac{a_{i3}^{(2)}}{a_{33}^{(2)}}.$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "jxoRHIRufO2h"
      },
      "source": [
        "Запишем систему в виде\n",
        "\n",
        "$$A^{3}x=b^{3},$$\n",
        "\n",
        "причем\n",
        "\n",
        "$$A^{(3)}=M_{3}A^{(2)},~~~b^{(3)}=M_{3}b^{(2)},$$\n",
        "\n",
        "где $M_{3}$ — нижняя треугольная матрица\n",
        "\n",
        "$$M_{3}=\\begin{pmatrix}\n",
        "1 & 0 & 0 & 0\\\\ \n",
        "0 & 1 & 0 & 0\\\\ \n",
        "0 & 0 & 1 & 0\\\\ \n",
        "0 & 0 & -m_{43} & 1\\\\ \n",
        "\\end{pmatrix}.$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8-mGjWK8fPIf"
      },
      "source": [
        "Тогда $A^{(3)}=M_{3}M_{1}M_{1}A$ есть верхняя треугольная матрица (ее и обозначим через $U$), и\n",
        "\n",
        "$$A=M_{1}^{-1}M_{2}^{-1}M_{3}^{-1}A^{(3)},$$\n",
        "\n",
        "$$b=M_{1}^{-1}M_{2}^{-1}M_{3}^{-1}b^{(3)}.$$\n",
        "\n",
        "Обозначим $L=M_{1}^{-1}M_{2}^{-1}M_{3}^{-1}$.\n",
        "\n",
        "Получим \n",
        "\n",
        "$$L=\\begin{pmatrix}\n",
        "1 & 0 & 0 & 0\\\\ \n",
        "m_{21} & 1 & 0 & 0\\\\ \n",
        "m_{31} & m_{32} & 1 & 0\\\\ \n",
        "m_{41} & m_{42} & m_{43} & 1\\\\ \n",
        "\\end{pmatrix}.$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RBMDCcwxfPIh"
      },
      "source": [
        "Таким образом, мы получили разложение\n",
        "\n",
        "$$A=LU,$$\n",
        "\n",
        "где \n",
        "\n",
        "$$U=\\begin{pmatrix}\n",
        "a_{11} & a_{12} & a_{13} & a_{14}\\\\ \n",
        "0 & a_{22}^{(1)} & a_{23}^{(1)} & a_{24}^{(1)}\\\\ \n",
        "0 & 0 & 0 & a_{34}^{(2)}\\\\ \n",
        "0 & 0 & 0 & a_{44}^{(3)}\\\\ \n",
        "\\end{pmatrix}.$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9FSLUTWMfPIl"
      },
      "source": [
        "В общем виде формулы нахождения элементов матриц $U$ (обозначим их теперь как $u_{ij}$) и $L$ (обозначим их теперь как $l_{ji}$) можно записать как\n",
        "\n",
        "$$u_{1j}=a_{1j},$$\n",
        "$$l_{j1}=\\frac{a_{j1}}{u_{11}}, \\; u_{11}\\neq0, \\; j = 1,...,n.$$\n",
        "\n",
        "Для $i = 2,...,n$:\n",
        "\n",
        "$$u_{ij}=a_{ij}-\\sum_{k=1}^{i-1}l_{ik}u_{ki},$$\n",
        "$$l_{ji}=\\frac{1}{u_{11}}(a_{ji}-\\sum_{k=1}^{i-1}l_{jk}u_{ki}),\\; j = i,...,n.$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "bRNo4Nv6fPIm"
      },
      "source": [
        "__Пример__\n",
        "\n",
        "Решим систему уравнений \n",
        "\n",
        "$$\\begin{cases}\n",
        "2x_{1}+x_{2}-x_{3}=5, \\\\\n",
        "4x_{1}-6x_{2}-2x_{3}=-2, \\\\\n",
        "-2x_{1}+7x_{2}-3x_{3}=7\n",
        "\\end{cases}$$\n",
        "\n",
        "методом $LU$-разложения."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "miRYjG2afPIo"
      },
      "source": [
        "Матрица коэффициентов $A$ будет иметь вид\n",
        "\n",
        "$$\\begin{pmatrix}\n",
        "2 & 1 & -1 \\\\ \n",
        "4 & -6 & -2 \\\\ \n",
        "-2 & 7 & -3\n",
        "\\end{pmatrix}.$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "mLu52LrLfPJs"
      },
      "source": [
        "Начнем прямой ход метода Гаусса. Для этого домножим первую строку на $2$ и вычтем ее из второго уравнения. При этом запишем в матрицу $L$ на место элемента $l_{21}$ значение $2$. Затем нам нужно вычесть из третьего уравнения первое, домноженное на $(-1)$. Значит, в матрицу $L$ запишем $l_{31}=-1$. \n",
        "\n",
        "Матрица коэффициентов будет иметь вид\n",
        "\n",
        "$$\\begin{pmatrix}\n",
        "2 & 1 & -1 \\\\ \n",
        "0 & -8 & 0 \\\\ \n",
        "0 & 8 & -4\n",
        "\\end{pmatrix},$$\n",
        "\n",
        "а матрица $L$ —\n",
        "\n",
        "$$\\begin{pmatrix}\n",
        "1 & 0 & 0 \\\\ \n",
        "2 & 1 & 0 \\\\ \n",
        "-1 & l_{32} & 1\n",
        "\\end{pmatrix}.$$"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "G4xiqpD8nyW9"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ObixYIZ0fPJt"
      },
      "source": [
        "Далее умножим вторую строку на $(-1)$ и вычтем ее из третьей. При этом в матрицу $L$ на место $l_{32}$ запишем $-1$.\n",
        "\n",
        "В итоге получим\n",
        "\n",
        "$$U=\\begin{pmatrix}\n",
        "2 & 1 & -1 \\\\ \n",
        "0 & -8 & 0 \\\\ \n",
        "0 & 0 & -4\n",
        "\\end{pmatrix},$$\n",
        "\n",
        "$$L=\\begin{pmatrix}\n",
        "1 & 0 & 0 \\\\ \n",
        "2 & 1 & 0 \\\\ \n",
        "-1 & -1 & 1\n",
        "\\end{pmatrix}.$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Z4U23qppfPJv"
      },
      "source": [
        "Решим теперь систему \n",
        "\n",
        "$$Ly=b:$$\n",
        "\n",
        "$$\\begin{cases}\n",
        "y_{1}=5, \\\\\n",
        "2y_{1}+y_{2}=-2, \\\\\n",
        "-y_{1}-y_{2}+y_{3}=7.\n",
        "\\end{cases}$$\n",
        "\n",
        "$$y_{1}=5,$$\n",
        "$$y_{2}=-12,$$\n",
        "$$y_{3}=0.$$\n",
        "\n",
        "И затем систему\n",
        "\n",
        "$$Ux=y:$$\n",
        "\n",
        "$$\\begin{cases}\n",
        "2x_{1}+x_{2}-x_{3}=5, \\\\\n",
        "-8x_{2}=-12, \\\\\n",
        "-4x_{3}=0.\n",
        "\\end{cases}$$\n",
        "\n",
        "$$x_{3}=0,$$\n",
        "$$x_{2}=1.5,$$\n",
        "$$x_{1}=1.75.$$\n",
        "\n",
        "Произведем проверку, подставив полученные значения переменных в исходную систему:\n",
        "\n",
        "$$\\begin{cases}\n",
        "2\\cdot1.75+1.5-0=5, \\\\\n",
        "4\\cdot1.75-6\\cdot1.5-2\\cdot0=-2, \\\\\n",
        "-2\\cdot1.75+7\\cdot1.5-3\\cdot0=7.\n",
        "\\end{cases}$$\n",
        "\n",
        "Таким образом, найденное решение верно."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "6tByBoGYfPJz"
      },
      "source": [
        "Метод представляется достаточно сложным, так как перед решением необходимо произвести разложение исходной матрицы коэффициентов на произведение верхней и нижней диагональных матриц. Количество операций, необходимых для разложения матрицы на произведение $LU$, — $O(n^{3})$ (как и при классическом методе Гаусса), а для решения двух треугольных систем — $O(n^{2})$, то есть прямой ход на порядок сложнее обратного. Использование метода оправдано в тех случаях, когда небходимо решить большое количество систем уравнений с одной и той же матрицей коэффициентов, но с меняющимися правыми частями. Такие задачи нередко встречаются на практике. В этом случае вместо того, чтобы каждый раз делать проход по методу Гаусса сложностью $O(n^{3})$, можно единожды произвести $LU$-разложение матрицы коэффициентов $A$, и для решения системы с новым вектор-столбцом свободных членов будет достаточно сделать два прохода прямых подстановок сложностью $O(n^{2})$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "UuNQrnk_fPJ0"
      },
      "source": [
        "### Метод Холецкого"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1cI5YX0NfPJ2"
      },
      "source": [
        "Рассмотрим несколько следствий из теоремы об $LU$-разложении."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "rCtTRPSXfPJ3"
      },
      "source": [
        "__Следствие 1__\n",
        "\n",
        "Если выполнены все условия теоремы и матрица $A$ невырождена, тогда существует и единственное разложение\n",
        "\n",
        "$$A=LDU^{(1)},$$\n",
        "\n",
        "где $L$ и $U^{(1)}$ — соответственно нижняя и верхняя треугольные матрицы с единицами на главной диагонали, а $D$ — диагональная матрица."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "U482cDzPfPJ5"
      },
      "source": [
        "__Следствие 2__\n",
        "\n",
        "Если выполены все условия Следствия 1, и, кроме того, матрица $A$ симметрична, тогда существует единственное разложение\n",
        "\n",
        "$$A=LDL^{T},$$\n",
        "\n",
        "где $L$ — нижняя треугольная матрица с единицами на главной диагонали, а $D$ — диагональная матрица."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "mxOCWH0QfPJ7"
      },
      "source": [
        "__Следствие 3__\n",
        "\n",
        "Если выполнены все условия Следствия 2, а кроме того, матрица $A$ _положительно определенная_ (все ее собственные значения положительны), тогда существует единственная нижная треугольная матрица $L$, такая, что\n",
        "\n",
        "$$A=LL^{T}.$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5ofConfEfPJ_"
      },
      "source": [
        "Метод Холецкого — еще один способ решения систем линейных уравнений, связанный с преобразованием матрицы коэффициентов к треугольной форме. Также известен как _метод квадратного корня_."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ntPTDHbnfPKB"
      },
      "source": [
        "Он заключается в разложении матрицы $A$ (при соблюдении условий ее симметричности и положительной определенности) на произведение матриц $LL^{T}$, описанном в Следствии 3. В этом разложении $L$ — нижняя треугольная матрица со строго положительными элементами на диагонали."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Xfcxt_t7fPKC"
      },
      "source": [
        "После получения разложения, аналогично методу $LU$-разложения, нужно представить систему уравнений в матричной форме как\n",
        "\n",
        "$$Ax=LL^{T}x=Ly=b$$\n",
        "\n",
        "и затем методом прямой подстановки решить последовательно две простые системы, характеризующиеся треугольными матрицами коэффициентов:\n",
        "\n",
        "$$Ly=b,$$\n",
        "$$L^{T}x=y.$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hd2OpLh1fPKD"
      },
      "source": [
        "Найдем искомое разложениие.\n",
        "\n",
        "Из условия разложения, имея в виду правила умножения матриц, получаем\n",
        "\n",
        "$$a_{ij}=\\sum_{k=1}^{n}l_{ik}l_{kj}^{T},$$\n",
        "\n",
        "где $l_{ij}$ и $l_{ij}^{T}$ — элементы матриц $L$ и $L^{T}$ соответственно ($l_{ij}^{T}=l_{ji}$)."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "CMVyont-fPKE"
      },
      "source": [
        "В частности, при $i<j$ получим \n",
        "\n",
        "$$a_{ij}=\\sum_{k=1}^{j-1}l_{ik}l_{jk},$$\n",
        "\n",
        "$$l_{ij}=\\frac{1}{l_{jj}}\\left( a_{ij}-\\sum_{k=1}^{j-1}l_{ik}l_{jk}\\right ).$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "XnFL3w_ZfPKF"
      },
      "source": [
        "При $i=j$:\n",
        "\n",
        "$$a_{ij}=\\sum_{k=1}^{i-1}l_{ik}^{2}+l_{ii}^{2}~~\\Rightarrow$$\n",
        "\n",
        "$$l_{ii}=\\sqrt{a_{ii}-\\sum_{k=1}^{i-1}l_{ik}^{2}}.$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NbdzLr_XfPKI"
      },
      "source": [
        "Если $A$ — вещественная симметричная положительно определенная матрица, то выражение под корнем будет всегда положительно."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ogYcA0McfPKK"
      },
      "source": [
        "Таким образом, элементы матрицы $L$ для нахождения $LL^{T}$-разложения вычисляются по следуюшим формулам:\n",
        "\n",
        "$$l_{ii}=\\sqrt{a_{ii}-\\sum_{k=1}^{i-1}l_{ik}^{2}},$$\n",
        "$$l_{ij}=\\frac{1}{l_{jj}}\\left( a_{ij}-\\sum_{k=1}^{j-1}l_{ik}l_{jk}\\right ), \\; j < i.$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "D627ux3xfPKO"
      },
      "source": [
        "__Пример__\n",
        "\n",
        "Решить методом Холецкого систему уравнений\n",
        "\n",
        "$$\\begin{cases}\n",
        "2x_{1}+x_{2}+4x_{3}=16, \\\\\n",
        "x_{1}+x_{2}+3x_{3}=12, \\\\\n",
        "4x_{1}+3x_{2}+14x_{3}=52.\n",
        "\\end{cases}$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "fXTc7djCfPKQ"
      },
      "source": [
        "Произведем разложение на $LL^{T}$:\n",
        "\n",
        "$$l_{11}=\\sqrt{a_{11}}=\\sqrt{2},$$\n",
        "$$l_{21}=\\frac{a_{21}}{l_{11}}=\\frac{1}{\\sqrt{2}},$$\n",
        "$$l_{31}=\\frac{a_{31}}{l_{11}}=\\frac{4}{\\sqrt{2}},$$\n",
        "\n",
        "$$l_{22}=\\sqrt{a_{22}-l_{21}^{2}}=\\sqrt{1 - \\frac{1}{2}}=\\frac{1}{\\sqrt{2}},$$\n",
        "$$l_{32}=\\frac{1}{l_{22}}\\left ( a_{32}-l_{21}l_{31} \\right)=\\sqrt{2}\\left ( 3 - \\frac{1}{\\sqrt{2}}\\cdot \\frac{4}{\\sqrt{2}} \\right )=\\sqrt{2},$$\n",
        "\n",
        "$$l_{33}=\\sqrt{a_{33}-l_{31}^{2}-l_{32}^{2}}=\\sqrt{14-8-2}=2.$$\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NOxrKaICfPKT"
      },
      "source": [
        "Получили матрицу \n",
        "\n",
        "$$L = \\begin{pmatrix}\n",
        "\\sqrt{2} & 0 & 0 \\\\ \n",
        "\\frac{1}{\\sqrt{2}} & \\frac{1}{\\sqrt{2}} & 0 \\\\ \n",
        "\\frac{4}{\\sqrt{2}} & \\sqrt{2} & 2\n",
        "\\end{pmatrix}, \n",
        "\\; \\; \n",
        "L^{T} = \\begin{pmatrix}\n",
        "\\sqrt{2} & \\frac{1}{\\sqrt{2}} & \\frac{4}{\\sqrt{2}} \\\\ \n",
        "0 & \\frac{1}{\\sqrt{2}} & \\sqrt{2} \\\\ \n",
        "0 & 0 & 2\n",
        "\\end{pmatrix}.$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3JC07czjfPKV"
      },
      "source": [
        "Решим систему $Ly=b:$\n",
        "\n",
        "$$\\begin{cases}\n",
        "\\sqrt{2}y_{1}=16, \\\\\n",
        "\\frac{1}{\\sqrt{2}}y_{1}+\\frac{1}{\\sqrt{2}}y_{2}=12, \\\\\n",
        "\\frac{4}{\\sqrt{2}}y_{1}+\\sqrt{2}y_{2}+2y_{3}=52.\n",
        "\\end{cases}$$\n",
        "\n",
        "$$y_{1} = 8\\sqrt{2},$$\n",
        "\n",
        "$$y_{2}=12\\sqrt{2}-8\\sqrt{2}=4\\sqrt{2},$$\n",
        "\n",
        "$$y_{3}=\\frac{52-32-8}{2}=6.$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "MK4RaNxffPKX"
      },
      "source": [
        "И решим систему $L^{T}x=y:$\n",
        "\n",
        "$$\\begin{cases}\n",
        "\\sqrt{2}x_{1}+\\frac{1}{\\sqrt{2}}x_{2}+\\frac{4}{\\sqrt{2}}x_{3}=8\\sqrt{2}, \\\\\n",
        "\\frac{1}{\\sqrt{2}}x_{2}+\\sqrt{2}x_{3}=4\\sqrt{2}, \\\\\n",
        "2x_{3}=6.\n",
        "\\end{cases}$$\n",
        "\n",
        "$$x_{3}=3,$$\n",
        "\n",
        "$$x_{2}=8-2\\cdot3=2,$$\n",
        "\n",
        "$$x_{1}=\\frac{16-12-2}{2}=1.$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BKOIO_3EfPKZ"
      },
      "source": [
        "Осуществим проверку, подставив полученные значения в исходную систему:\n",
        "\n",
        "$$\\begin{cases}\n",
        "2\\cdot1+2+4\\cdot3=16, \\\\\n",
        "1+2+3\\cdot3=12, \\\\\n",
        "4\\cdot1+3\\cdot2+14\\cdot3=52.\n",
        "\\end{cases}$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qHxlLF5CfPKa"
      },
      "source": [
        "Как и $LU$-разложение, этот метод более производителен, чем обычный метод Гаусса, в связи с чем часто используется для решения инженерных задач. Вычисление по формулам нахождения $l_{ii}$ и $l_{ij}$ будут иметь сложность $\\frac{1}{3}n^{3}+O(n^{2})$, и затем после разложения производится обратный ход метода Гаусса со сложностью $O(n^{2})$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1yNJ7MTJfPKc"
      },
      "source": [
        "Существует большое количество других методов решения СЛАУ. С ними, в частности, можно ознакомиться в книге «Вычислительные методы линейной алгебры» (номер 2 в списке литературы)."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "6hmx96_WfPKd"
      },
      "source": [
        "## Практическое задание"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ZBi7FV66fPKf"
      },
      "source": [
        "__1.__ Решить систему уравнений методом Крамера:\n",
        "\n",
        "   а) $\\begin{cases}\n",
        "x_{1}-2x_{2}=1 \\\\\n",
        "3x_{1}-4x_{2}=7\n",
        "\\end{cases}$\n",
        "    \n",
        "   б) $\\begin{cases}\n",
        "2x_{1}-x_{2}+5x_{3}=10 \\\\\n",
        "x_{1}+x_{2}-3x_{3}=-2 \\\\\n",
        "2x_{1}+4x_{2}+x_{3}=1\n",
        "\\end{cases}$\n",
        "\n",
        "__2*.__ Найти $L$-матрицу $LU$-разложения для матрицы коэффициентов:\n",
        "\n",
        "   а)$$\\begin{pmatrix}\n",
        "1 & 2 & 4 \\\\ \n",
        "2 & 9 & 12 \\\\ \n",
        "3 & 26 & 30\n",
        "\\end{pmatrix}$$\n",
        "    \n",
        "   б)$$\\begin{pmatrix}\n",
        "1 & 1 & 2 & 4\\\\ \n",
        "2 & 5 & 8 & 9\\\\ \n",
        "3 & 18 & 29 & 18\\\\\n",
        "4 & 22 & 53 & 33\n",
        "\\end{pmatrix}$$\n",
        "    \n",
        "__3*.__ Решить систему линейных уравнений методом $LU$-разложения\n",
        "\n",
        "$$\\begin{cases}\n",
        "2x_{1}+x_{2}+3x_{3}=1 \\\\\n",
        "11x_{1}+7x_{2}+5x_{3}=-6 \\\\\n",
        "9x_{1}+8x_{2}+4x_{3}=-5\n",
        "\\end{cases}$$\n",
        "\n",
        "__4*.__ Решить систему линейных уравнений методом Холецкого\n",
        "\n",
        "$$\\begin{cases}\n",
        "81x_{1}-45x_{2}+45x_{3}=531 \\\\\n",
        "-45x_{1}+50x_{2}-15x_{3}=-460 \\\\\n",
        "45x_{1}-15x_{2}+38x_{3}=193\n",
        "\\end{cases}$$\n",
        "\n",
        "__5*.__ Написать на Python программу с реализацией одного из изученных алгоритмов решения СЛАУ."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ShwjcAO-i0u1"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Hs_r_WNhfPKg"
      },
      "source": [
        "## Литература"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "JjYy5eCjfPKh"
      },
      "source": [
        "1. Ильин В. А., Позняк Э. Г. Линейная алгебра: Учеб. для вузов. — 6-е изд. — М.: Физматлит, 2005.\n",
        "\n",
        "2. Фаддеев Д. К., Фаддеева В. Н. Вычислительные методы линейной алгебры. М.: ГИФМЛ, 1960.\n",
        "\n",
        "3. Рябушко А. П., Сборник индивидуальных заданий по высшей математике. Часть 1. Минск: Вышэйшая школа, 1990.\n",
        "\n",
        "4. Форсайт Дж., Молер К. Численное решение систем линейных алгебраических уравнений. М.: Мир, 1969."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "YNfZHfSsfPKi"
      },
      "source": [
        "## Дополнительные материалы"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "dzIGKA4kfPKj"
      },
      "source": [
        "1. Островский А. М. Решение уравнений и систем уравнений. М.: Издательство иностранной литературы, 1963.\n",
        "2. [Критерий положительной определенности матрицы](http://twt.mpei.ac.ru/math/LARB/Quadrf/LA_06030300.html).\n",
        "3. [Доказательство правила Крамера](http://portal.tpu.ru/SHARED/k/KONVAL/Sites/Russian_sites/2/18.htm)."
      ]
    }
  ]
}